#define _CRT_SECURE_NO_WARNINGS


//
//class PalindromeList {
//public:
//    struct ListNode* reverseList(struct ListNode* head) {
//        struct ListNode* cur = head;
//        struct ListNode* prev = nullptr;
//
//        while (cur)
//        {
//            struct ListNode* tmp = cur->next;
//            cur->next = prev;
//            prev = cur;
//            cur = tmp;
//        }
//
//        return prev;
//    }
//
//    struct ListNode* middleNode(struct ListNode* head) {
//        struct ListNode* fast = head, * slow = head;
//
//        while (fast && fast->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//        }
//
//        return slow;
//    }
//
//
//    bool chkPalindrome(ListNode* A) {
//        // write code here
//        struct ListNode* mid = middleNode(A);
//        struct ListNode* rlist = reverseList(mid);
//
//        while (rlist)
//        {
//            if (A->val != rlist->val) return false;
//
//            A = A->next;
//            rlist = rlist->next;
//        }
//
//        return true;
//    }
//};
//
//


//
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        struct ListNode* nhead = (struct ListNode*)malloc(sizeof(struct ListNode));
//        struct ListNode* rhead = (struct ListNode*)malloc(sizeof(struct ListNode));
//
//        nhead->next = NULL, rhead->next = NULL;
//        struct ListNode* cur = pHead, * cur1 = nhead, * cur2 = rhead;
//
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                cur1->next = cur;
//                cur1 = cur1->next;
//            }
//            else
//            {
//                cur2->next = cur;
//                cur2 = cur2->next;
//            }
//            cur = cur->next;
//        }
//
//        cur1->next = rhead->next;
//        cur2->next = NULL;
//        struct ListNode* newhead = nhead->next;
//
//        free(nhead);
//        free(rhead);
//
//        return newhead;
//    }
//};
